# -*- coding:utf-8 -*- 
__date__ = '2022/6/27 1:23 下午'
'''
链表的反转
'''


class ListNode(object):
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
    if isinstance(val, int):
      self.val = val
      self.next = next
    elif isinstance(val, list):
      self.val = val[0]
      self.next = None
      head = self
      for i in range(1, len(val)):
        node = ListNode(val[i])
        head.next = node
        head = head.next


class Solution:
  def printNode(self, next):
    while next:
      print(next.val, end=' -> ')
      next = next.next
    print('\n')

  def reverseList(self, head):
    # 遍历，当前节点的next是上一个节点
    # 记录上一个节点
    pre = None
    # 保存当前链表
    curr = head
    while curr != None:
      # 保存下一个节点
      next = curr.next
      curr.next = pre
      pre = curr
      # cur向后移动
      curr = next
    self.printNode(pre)

  def reverseList1(self, head):
    # 递归处理
    if head == None or head.next == None:
      return head
    last = self.reverseList1(head.next)
    head.next.next = head
    head.next = None
    return last


if __name__ == '__main__':
  list1 = [1, 2, 10, 343, 400]
  # list2 = [-10. -6,0, 450]
  ls1 = ListNode(list1)
  # ls2 = ListNode(list2)
  # Solution = Solution()
  # Solution.printNode(ls1)
  # Solution.reverseList(ls1)
  head = Solution.reverseList1(ls1)
  # Solution.printNode(head)
